package com.lijing.ShellSort;

import com.lijing.StopWatch.StopWatch;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
import java.util.concurrent.CompletableFuture;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr1 = {8,9,1,7,2,3,5,4,6,0,30,12,24,45,34,22,11};
        shellSort1(arr1);
        System.out.println(Arrays.toString(arr1));

        int[] arr = new int[800000];
        for (int i = 0; i < 800000; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }
        StopWatch sw = new StopWatch();
        shellSort1(arr);
        double time = sw.elapsedTime();
        //System.out.println(Arrays.toString(arr));
        System.out.println("Cost time:"+time+"s");

    }

    /**
     * 希尔排序
     * 将待排序的数组，每次二等分，直到分为一个数组，分组的数组分别进行插入排序
     * @param arr 待排序的数组
     */
    public static void shellSort(int[] arr){
        int groupCnt = arr.length/2;
        int itemCount;
        int insertValue;
        int insertIndex;
        do{
            itemCount = arr.length/groupCnt;
            for (int i = 0; i < groupCnt; i++) {//分为groupCnt
                //插入排序
                for (int j = i+groupCnt; j < i+groupCnt*itemCount; j+=groupCnt) {
                    insertValue = arr[j];
                    insertIndex = j-groupCnt;
                    while (insertIndex >= i && (insertValue < arr[insertIndex])){
                        arr[insertIndex + groupCnt] = arr[insertIndex];
                        insertIndex -= groupCnt;
                    }
                    arr[insertIndex+groupCnt] = insertValue;
                }
            }
        }while((groupCnt= groupCnt/2) >= 1);
    }

    public static void shellSort1(int[] arr){
        int step = 1;
        while(step<arr.length/2){
            step = 2*step+1;
        }
        for (int gap = step; gap > 0; gap /= 2){//增量gap,并逐步缩小增量
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j-gap]){
                    while (j-gap >= 0 && temp < arr[j-gap]){
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }

        }
    }
}
